//
// Created by yangchao on 2022/4/23.
// 15. 三数之和: https://leetcode-cn.com/problems/3sum/
//
#include <vector>
#include <algorithm>
using namespace std;

class ThreeSum {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3) return {};
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        int len = nums.size();
        for (int i = 0; i < len-2; ++i) {   //固定一个数，转为求两数之和
            if (nums[i] > 0) return res;    //第一个大于0.后面肯定都大于0
            if (i > 0 &&nums[i] == nums[i-1]) continue; //去重
            // 双指针在nums[i]后面的区间中寻找和为-nums[i]的两个数
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                if (nums[left] + nums[right] < -nums[i]) {
                    left++;
                } else if (nums[left] + nums[right] > -nums[i]) {
                    right--;
                } else {
                    res.push_back(vector<int> {nums[i],nums[left],nums[right]});
                    left++;
                    right--;
                    //去重复
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                }
            }
        }
        return res;
    }
};

